package binarytree;

import java.util.*;

/**
 * 二叉搜索树与双向链表
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
 * 解题思想：排好序的搜索树-》中序遍历的思想
 * 双向链表-》left作为前驱 right 作为后继
 */

 class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
public class Solution {
     TreeNode prev=null;
    public void ConvertChild(TreeNode pCur){
        if(pCur==null)
        return;
        ConvertChild(pCur.left);
    
        pCur.left=prev;
        if(prev!=null){
        prev.right=pCur;
        }
        prev=pCur;
        ConvertChild(pCur.right);

    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree ==null)
        return null;
        ConvertChild(pRootOfTree);
        TreeNode head=pRootOfTree;
        while(head.left!=null){
           head=head.left;
        }
        return head;
        
    }
    /**
     * 1.定义 preIndex遍历前序遍历这个数组
     * 2.在中序遍历的inbegin(ib)~inend(ie)之间，找到ri的下标位置
     * 3.此时ri左边的就是左树，ri右边的就是右树
     * 4.递归创建左树，递归创建右树
     * 5.ib>ie的时候，说明没有了左树或者右树
     */
    public int preIndex = 0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend){
        if(inbegin>inend) return null;//说明此时没有左树或右树
        TreeNode root = new TreeNode(preorder[preIndex]);
        //1.找到根节点在中序遍历当中的位置
        int rootIndex= findInorderRootIndex(inorder,inbegin,inend,preorder[preIndex]);
        preIndex++;
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    private int findInorderRootIndex(int[] inorder,int inbegin,int inend,int val){
        for(int i=inbegin;i<=inend;i++){
            if(inorder[i]==val)
                return i;
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);

    }

    /**
     * 根据二叉树创建字符串
     * @param t
     * @param sb
     */
    public void tree2strChild(TreeNode t,StringBuilder sb){
        if(t==null) return;
        sb.append(t.val);
        if(t.left !=null){
            sb.append('(');
            tree2strChild(t.left,sb);
            sb.append(')');
        }else{
            if(t.right==null){
                return;
            }else{
                sb.append("()");
            }

        }
        if(t.right==null){
            return;

        }else{
            sb.append('(');
            tree2strChild(t.right,sb);
            sb.append(')');

        }

    }
    public String tree2str(TreeNode root) {
        if(root==null) return null;
        StringBuilder sb = new StringBuilder();
        tree2strChild(root,sb);
        return sb.toString();

    }
}
